package com.company;

/**
 * 687. 最长同值路径
 * 给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
 */

public class Solution687 {
    int maxTime=0;
    public int longestUnivaluePath(TreeNode root) {
        if (root==null) return 0;
        int a=getMaxVal(root,root.val);
        return maxTime;
    }

    public int getMaxVal(TreeNode root,int val){
        if (root==null) return 0;
        int left=getMaxVal(root.left,root.val);
        int right=getMaxVal(root.right,root.val);
        //比较
        maxTime=Math.max(maxTime,left+right);
        if(root.val== val)
        {
            //与父节点值相同，直接+1
            return Math.max(left,right)+1;
        }
        return 0;
    }

    public static void main(String[] args) {

    }
}

class TreeNode {
    int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
     TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
     }
  }
